/**
 * @a https://leetcode.cn/problems/reverse-pairs/
 */

#include "common.h"

class Solution
{
public:
    int reversePairs(vector<int> &nums)
    {
        tmp.resize(nums.size());
        mergeSort(nums.begin(),nums.end());
        return _ret;
    }
    void mergeSort(vector<int>::iterator begin, vector<int>::iterator end){
        int sz = end - begin;
        if(sz <= 1) return;

        auto mid = begin + (sz >> 1);
        mergeSort(begin, mid);
        mergeSort(mid, end);
        
        auto cur1 = begin, cur2 = mid;
        while(cur1 < mid && cur2 < end){
            if(*cur1 <= ((long long)(*cur2) << 1)){
                ++cur2;
            }
            else{
                _ret += end - cur2;
                ++cur1;
            }
        }
        int i = 0;cur1 = begin,cur2 = mid;
        while(cur1 < mid && cur2 < end){
            if(*cur1 <= *cur2){
                tmp[i++] = *cur2++;
            }
            else{
                tmp[i++] = *cur1++;
            }
        }
        while(cur1 < mid) tmp[i++] = *cur1++;
        while(cur2 < end) tmp[i++] = *cur2++;

        copy(tmp.begin(), tmp.begin() + sz, begin);
    }
private:
    int _ret = 0;
    vector<int> tmp;

};